﻿using System;

namespace Sortering
{
    partial class Array
    {
        private static int Partition(int[] array, int left, int right)
        {
            int i = left, j = right;
            int pivot = array[(left + right) / 2];
            
            while (i <= j)
            {
                while (array[i] < pivot)
                {
                    i++;
                }
                while (array[j] > pivot)
                {
                    j--;
                }

                if (i <= j)
                {
                    Swap(array, i, j);
                    i++;
                    j--;
                }
            }

            return i;
        }
        private static int Partition(IComparable[] array, int left, int right)
        {
            int i = left, j = right;
            IComparable pivot = array[(left + right) / 2];

            while (i <= j)
            {
                while (array[i].CompareTo(pivot) < 0)
                {
                    i++;
                }
                while (array[j].CompareTo(pivot) > 0)
                {
                    j--;
                }

                if (i <= j)
                {
                    Swap(array, i, j);
                    i++;
                    j--;
                }
            }

            return i;
        }
        public static void QuickSort(int[] array)
        {
            QuickSort(array, 0, array.Length - 1);
        }
        public static void QuickSort(IComparable[] array)
        {
            QuickSort(array, 0, array.Length - 1);
        }
        public static void QuickSort(int[] array, int left, int right)
        {
            int index = Partition(array, left, right);
            if (left < index-1)
            {
                QuickSort(array, left, index - 1);
            }
            if (index < right)
            {
                QuickSort(array, index, right);
            }
        }
        public static void QuickSort(IComparable[] array, int left, int right)
        {
            int index = Partition(array, left, right);
            if (left < index - 1)
            {
                QuickSort(array, left, index - 1);
            }
            if (index < right)
            {
                QuickSort(array, index, right);
            }
        }
    }
}
